package uns.fit.gis.alg;

import uns.fit.gis.mapobj.Segment;

public class Heap {
	private Segment[] heapArray;

	private int maxSize;

	private int currentSize; // number of items in array

	public Heap(int mx) {
		maxSize = mx;
		currentSize = 0;
		heapArray = new Segment[maxSize];
	}

	public Segment remove() {
		Segment root = heapArray[0];
		heapArray[0] = heapArray[--currentSize];
		trickleDown(0);
		return root;
	}

	public void trickleDown(int index) {
		int largerChild;
		Segment top = heapArray[index];
		while (index < currentSize / 2) {
			int leftChild = 2 * index + 1;
			int rightChild = leftChild + 1;
			// find larger child
			if (rightChild < currentSize
					&& heapArray[leftChild].getLength() < heapArray[rightChild]
							.getLength())
				largerChild = rightChild;
			else
				largerChild = leftChild;

			if (top.getLength() >= heapArray[largerChild].getLength())
				break;

			heapArray[index] = heapArray[largerChild];
			index = largerChild;
		}
		heapArray[index] = top;
	}

	public void displayHeap() {
		int nBlanks = 32;
		int itemsPerRow = 1;
		int column = 0;
		int currentIndex = 0;
		while (currentSize > 0) {
			if (column == 0)
				for (int k = 0; k < nBlanks; k++)
					System.out.print(' ');
			System.out.print(heapArray[currentIndex].getLength());

			if (++currentIndex == currentSize) // done?
				break;

			if (++column == itemsPerRow) // end of row?
			{
				nBlanks /= 2;
				itemsPerRow *= 2;
				column = 0;
				System.out.println();
			} else
				for (int k = 0; k < nBlanks * 2 - 2; k++)
					System.out.print(' '); // interim blanks
		}
	}

	public void displayArray() {
		for (int j = 0; j < maxSize; j++)
			System.out.print(heapArray[j].getLength() + " ");
		System.out.println("");
	}

	public void insertAt(int index, Segment newNode) {
		heapArray[index] = newNode;
		currentSize ++;
	}

	public int size() {
		return currentSize;
	}
}
